1. Field of the Invention
The present invention relates to zero-knowledge proving techniques for proving the equality or inequality of (discrete logarithms, which is suitable for use in undeniable signatures.
2. Description of the Related Art
Undeniable signatures proposed by Chaum have an important property such that a signer cannot deny the validity of a self-generated signature but a forged signature. The undeniable signature schemes like this make use of the group operation of an order-q group G on modulo p, where p and q are prime and have a relationship of q|(p−1). When y=gx is an element of the group G, the signer uses the generator g as a public key and x as a private key. A signature on a message m is obtained by calculating SIG=mx, where x is the private key. For (m, SIG), the validity of the signature can be decided by proving the equality of the discrete logarithm x of the public key: y=gx and the discrete logarithm x′ of SIG=mx′. In contrast, the forgery of the signature can be decided by proving the inequality of SIG′ and mx for (m, SIG′). Accordingly, such signature system needs a proving mechanism for proving the equality or inequality the above discrete logarithms and a verifying mechanism for verifying the results in a designated group operation.
There has been known the Chaum's scheme that allows a prover to convince the verifier about the equality or inequality of SIG′ and mx, which is disclosed in “Zero-knowledge undeniable signatures”, Advances in Cryptology, Proceedings of Eurocrypt' 1990, LNCS473, Springer-Verlag, pp. 458–464, 1991. This Chaum's scheme, however, employs different proving systems to prove respective ones of the equality and inequality. Especially, the system of proving the inequality cannot be performed without the verifier and therefore it is impossible for the prover solely to prove the inequality.
There has been proposed another proving scheme that employs the same proving systems to prove both the equality and inequality. See “Efficient convertible undeniable signature schemes”, Proceedings of 4th Annual Workshop on Selected Areas in Cryptography, SAC'97, August 1997. Although this scheme allows the prover solely to prove both the equality and inequality and the efficiency thereof has been qualitatively analyzed, it has a disadvantage of leaking important information. More specifically, the information mx is known by the verifier, loading to a contradiction such that, when indicating that a message m is not signed, the signature on m is involuntarily passed.